/*
 * Graph.c
 *
 *  Created on: 12/02/2012
 *      Author: marcio
 */

#include "Graph.h"


Graph* graph_readGraph(FILE* filegraph){
	//TODO
	return NULL;
}

Graph* graph_complement(Graph* g){
	Graph* gc = graph_newGraph(g->n);
	int i,j;
	for(i = 0; i < gc->n; i++){
		for(i = 0; i < gc->n; i++){
			if(graph_hasEdge(g,i,j))graph_addEdge(gc, i, j);
		}
	}
	return gc;
}

Graph* graph_homophism(Graph* g, int* rename){
	//TODO
	return NULL;
}

int graph_degree(Graph* g, void* v){
	int i;
	int degree = 0;
	for(i = 0; i < g->n; i++){
		if(graph_hasEdge(g, v, g->mapping->keys[i]))degree++;
	}
	return degree;
}

void** graph_getNeigboorhood(Graph* g, void* v, int* d){
	void* neig = malloc(sizeof(void*)*graph_degree(g, v));
	int i, degree = 0;
	for(i = 0; i < g->n; i++){
		if(graph_hasEdge(g, g->mapping->keys[i], v))neig[degree++] = g->mapping->keys[i];
	}
	*d = degree;
	return neig;
}

void** graph_getAntiNeigboorhood(Graph* g, void* v, int* d){
	void* neig = malloc(sizeof(void*)*graph_degree(g, v));
	int i, degree = 0;
	for(i = 0; i < g->n; i++){
		if(!graph_hasEdge(g, g->mapping->keys[i], v))neig[degree++] = g->mapping->keys[i];
	}
	*d = degree;
	return neig;
}

void** graph_getCommunNeigboorhood(Graph* g, void** nodes, int r, int* d){
	int i,j;
	BitArray* ng = bitarray_NewBitArray(g->n);
	for(i = 0; i < g->n; i++){
		bitarray_setbit(ng,i);
	}
	for(i = 0; i < r; i++){
		for(j = 0; j < g->n; j++){
			if(!graph_hasEdge(g,nodes[i],g->mapping->keys[j])){
				bitarray_setbit(ng,i);
			}
		}
	}
	void** ret = malloc(sizeof(void*)*bitarray_conut1(ng));
	j = 0;
	for(i = 0; i < g->n; i++){
		if(bitarray_isset(ng, i))ret[j++] = g->mapping->key[i];
	}
	*d = j;
	return ret;
}

void** graph_getCommumAntiNeigboorhood(Graph* g, void** nodes, int r, int* d){
	int i,j;
	BitArray* ng = bitarray_NewBitArray(g->n);
	for(i = 0; i < g->n; i++){
		bitarray_setbit(ng,i);
	}
	for(i = 0; i < r; i++){
		for(j = 0; j < g->n; j++){
			if(graph_hasEdge(g,nodes[i],g->mapping->keys[j])){
				bitarray_unsetbit(ng,i);
			}
		}
	}
	void** ret = malloc(sizeof(void*)*bitarray_conut1(ng));
	j = 0;
	for(i = 0; i < g->n; i++){
		if(bitarray_isset(ng, i))ret[j++] = g->mapping->key[i];
	}
	*d = j;
	return ret;
}

void** graph_getTotalNeigboorhood(Graph* g, void** nodes, int r, int* d){
	int i,j;
	BitArray* ng = bitarray_NewBitArray(g->n);
	for(i = 0; i < g->n; i++){
		bitarray_unsetbit(ng,i);
	}
	for(i = 0; i < r; i++){
		for(j = 0; j < g->n; j++){
			if(graph_hasEdge(g,nodes[i],g->mapping->keys[j])){
				bitarray_setbit(ng,i);
			}
		}
	}
	void** ret = malloc(sizeof(void*)*bitarray_conut1(ng));
	j = 0;
	for(i = 0; i < g->n; i++){
		if(bitarray_isset(ng, i))ret[j++] = g->mapping->key[i];
	}
	*d = j;
	return ret;
}

void** graph_getTotalAntiNeigboorhood(Graph* g, void** nodes, int r, int* d){
	int i,j;
	BitArray* ng = bitarray_NewBitArray(g->n);
	for(i = 0; i < g->n; i++){
		bitarray_unsetbit(ng,i);
	}
	for(i = 0; i < r; i++){
		for(j = 0; j < g->n; j++){
			if(!graph_hasEdge(g,nodes[i],g->mapping->keys[j])){
				bitarray_setbit(ng,i);
			}
		}
	}
	void** ret = malloc(sizeof(void*)*bitarray_conut1(ng));
	j = 0;
	for(i = 0; i < g->n; i++){
		if(bitarray_isset(ng, i))ret[j++] = g->mapping->key[i];
	}
	*d = j;
	return ret;
}

void graph_breathFirstSeacrh(Graph* g, void* v, void (*action)(void*)){
	if(map_seachForKey(g->mapping, v)){
		int vind = map_getValue(g->mapping, v);
		int end = -1;
		char status[g->n];
		Queue* q = queue_newQueue();
		queue_add(q,vind);
		int i, j, k;
		for(i = 0; i < g->n; i++){
			status[i] = 'n';
		}
		do{
			u = *(queue_push(q));
			status[u] = 'v';
			action(g->mapping->keys[u]);
			for(i = 0; i < g->n; i++){
				if(graph_hasEdge(g, g->mapping->keys[i], g->mapping->keys[u]) && status[i]== 'n'){
					int node = i;
					status[i] = 's';
					queue_add(q,&node);
				}
			}
		}while(!queue_isEmpty(q));
	}
}

void graph_deepFirstSeacrh(Graph* g, void* v, void (*action)( void*)){
	if(map_seachForKey(g->mapping, v)){
		int vind = map_getValue(g->mapping, v);
		int end = -1;
		char status[g->n];
		Stack* s = stack_newStack();
		stack_add(s,vind);
		int i, j, k;
		for(i = 0; i < g->n; i++){
			status[i] = 'n';
		}
		status[vind] = 'v';
		do{
			u = *(stack_push(s))
			action(g->mapping->keys[u]);
			for(i = 0; i < g->n; i++){
				if(graph_hasEdge(g, g->mapping->keys[i], g->mapping->keys[u]) && status[i]== 'n'){
					int node = i;
					status[i] = 's';
					stack_add(s,&node);
				}
			}
		}while(!stack_isEmpty(s));
	}
}

void** graph_breathFirstList(Graph* g, void* v, int* d){
	if(map_seachForKey(g->mapping, v)){
		void** ret = malloc(sizeof(void*), g->n);
		int retsize = 0;
		int vind = map_getValue(g->mapping, v);
		int end = -1;
		char status[g->n];
		Queue* q = queue_newQueue();
		queue_add(q,vind);
		int i, j, k;
		for(i = 0; i < g->n; i++){
			status[i] = 'n';
		}
		ret[retsize++] = v;
		do{
			u = *(queue_push(q));
			status[u] = 'v';
			action(g->mapping->keys[u]);
			for(i = 0; i < g->n; i++){
				if(graph_hasEdge(g, g->mapping->keys[i], g->mapping->keys[u]) && status[i]== 'n'){
					int node = i;
					status[i] = 's';
					queue_add(q,&node);
					ret[retsize++] = g->mapping->keys[i];
				}
			}
		}while(!queue_isEmpty(q));
	}
	*d = retsize;
	return ret;
}


void** graph_deepFirstList(Graph* g, void* v, int* d){
	if(map_seachForKey(g->mapping, v)){
		int vind = map_getValue(g->mapping, v);
		void** ret = malloc(sizeof(void*), g->n);
		int retsize = 0;
		int end = -1;
		char status[g->n];
		Stack* s = stack_newStack();
		stack_add(s,vind);
		int i, j, k;
		for(i = 0; i < g->n; i++){
			status[i] = 'n';
		}
		status[vind] = 'v';
		do{
			u = *(stack_push(s))
			action(g->mapping->keys[u]);
			for(i = 0; i < g->n; i++){
				if(graph_hasEdge(g, g->mapping->keys[i], g->mapping->keys[u]) && status[i]== 'n'){
					int node = i;
					status[i] = 's';
					ret[retsize++] = g->mapping->keys[i];
					stack_add(s,&node);
				}
			}
		}while(!stack_isEmpty(s));
	}
	*d = retsize;
	return ret;
}


void** graph_getNodes(Graph* g, int* d){
	return g->mapping->keys;
}
